from typing import List


class Solution:
    """
    方法：回溯法，通过交换元素生成所有排列
    Args:
        nums: List[int] - 输入的整数列表
    Returns:
        List[List[int]] - 所有可能的排列组合
    Time: O(n*n!) - 共有n!种排列，每种排列需要O(n)时间复制
    Space: O(n) - 递归调用栈的深度为n
    """
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        n = len(nums)
        def backtrack(first: int) -> None:
            if(first == n):
                ans.append(nums.copy())
            for i in range(first, n):
                nums[first], nums[i] = nums[i], nums[first] #交换
                backtrack(first + 1)
                nums[first], nums[i] = nums[i], nums[first] #换回
        backtrack(0)
        return ans

# backtrack(0)

# ├─ i=0: [1,2,3]

# │  └─ backtrack(1)

# │     ├─ i=1: [1,2,3] → backtrack(2) → [1,2,3] ✅

# │     └─ i=2: [1,3,2] → backtrack(2) → [1,3,2] ✅

# ├─ i=1: [2,1,3]

# │  └─ backtrack(1)

# │     ├─ i=1: [2,1,3] → backtrack(2) → [2,1,3] ✅

# │     └─ i=2: [2,3,1] → backtrack(2) → [2,3,1] ✅

# └─ i=2: [3,2,1]

#    └─ backtrack(1)

#       ├─ i=1: [3,2,1] → backtrack(2) → [3,2,1] ✅

#       └─ i=2: [3,1,2] → backtrack(2) → [3,1,2] ✅
    """
    方法：回溯法
    Args:
        nums: List[int] - 输入的整数列表
    Returns:
        List[List[int]] - 所有可能的排列组合
    Time: O(n*n!) - 共有n!种排列，每种排列需要O(n)时间复制
    Space: O(n) - 递归调用栈的深度为n
    """
    def permute1(self, nums: List[int]) -> List[List[int]]:
        n = len (nums)
        ans = []
        path = [0] * n # 所有排列的长度都是一样的 n
        on_path = [False] * n
        def dfs(i: int) -> None:
            if i == n:
                ans.append(path.copy())
                return
            for j, on in enumerate(on_path):
                if not on:
                    path[i] = nums[j]
                    on_path[j] = True
                    dfs(i + 1)
                    on_path[j] = False
        dfs(0)
        return ans
